#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;


// class Solution {
// public:
//     vector<int> findAnagrams(string s, string p) {
//         int size_s = s.size();
//         int size_p = p.size();
//         vector<int> ret;
//         string example = p;
//         sort(example.begin(),example.end());
//         for(int i = 0;i < (size_s-size_p+1);i++)
//         {
//             string tmp;
//             for(int j = i;j < i+size_p;j++)
//             {
//                 tmp+=s[j];
//             }
//             sort(tmp.begin(),tmp.end());
//             if(tmp == example)
//                 ret.push_back(i);
//         }
//         return ret;
//     }
// };



// 1 核心依据异位词 “字符种类和数量完全一致” 的特性 用 26 维数组分别统计 p 的字符计数和 s 中滑动窗口的字符计数
// 2 先初始化 p 的字符计数数组 同时初始化 s 中第一个长度与 p 相同的窗口的字符计数数组
// 3 采用滑动窗口遍历 s 中所有可能的有效起始位置 滑动方式为窗口整体向右平移一位 无需重新统计整个窗口字符
// 4 滑动时仅更新边界字符计数 即移除当前窗口左边界的字符计数（该字符随窗口右移离开窗口） 
//     再加入下一个窗口右边界的新字符计数（该字符随窗口右移进入窗口）
// 5 每个窗口均通过对比计数数组判断是否为异位词 匹配则记录当前起始位置
// 6 最后一个窗口无需滑动 避免越界 最终收集所有匹配的起始位置作为结果
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int size_s = s.size();
        int size_p = p.size();
        vector<int> ret;

        // 边界处理：s长度小于p，直接返回空
        if (size_s < size_p)
            return ret;

        // 用数组统计字符计数
        vector<int> example(26, 0);
        vector<int> window(26, 0);

        for (int i = 0; i < size_p; i++) 
        {
            example[p[i] - 'a']++;
            window[s[i] - 'a']++;
        }

        for(int i=0; i<size_s-size_p+1;i++)
        {
            if(example == window)
                ret.push_back(i);
            if(i + size_p < size_s)
            {
                window[s[i] - 'a']--;
                window[s[i + size_p] - 'a']++;
            }
        }
        return ret;
    }
};
